#include <vector>
using namespace std;
#include <set>
#include <algorithm>


// version 1 
class Solution {
public:
//从第一个示例看出来：如果有相同的，就要放在第一个位置 [左区间 < target][右区间 >= target]
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size();
        while(left < right){
            int mid = left + (right - mid) / 2;
            if(nums[mid] >= target) right = mid;
            else left = ++mid;
        }
        return left;
    }
};